package com.Questions.DP;

import java.util.*;
/**
 * 青蛙过河
 */
public class leetcode403 {
    public boolean canCross1(int[] stones) {
        // dp[i][j] 表示 青蛙能跳到位置为i的石头上 并且能跳j个单位
        // dp[i][j] = dp[i-j][j] || dp[i-j-1][j+1] || dp[i-j+1][j-1]
        // dp[0] dp[1]
        if(stones[1] - stones[0] > 1){
            return false;
        }
        int n = stones.length;
        int maxNum = stones[n - 1];
        if(maxNum >= Integer.MAX_VALUE) {
            return false;
        }
        boolean[][] dp = new boolean[maxNum + 1][n + 1];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], false);
        }
        dp[0][1] = true;
        dp[1][0] = true;
        dp[1][1] = true;
        dp[1][2] = true;
        for (int i = 2; i < n; i++) {
            int cur = stones[i];
            for (int j = 1; j < n; ++j) {
                if (cur - j >= 0 && dp[cur - j][j]){
                    dp[cur][j] = true;
                }
                if (cur - j - 1 >= 0 && dp[cur - j - 1][j + 1]){
                    dp[cur][j] = true;
                }
                if (cur - j + 1 >= 0 && dp[cur - j + 1][j - 1]){
                    dp[cur][j] = true;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (dp[maxNum][i]) {
                return true;
            }
        }
        return false;
    }

    public boolean canCross(int[] stones) {
        int n = stones.length;
        boolean[][] dp = new boolean[n][n];
        dp[0][0] = true;
        for (int i = 1; i < n; ++i) {
            if (stones[i] - stones[i - 1] > i) {
                return false;
            }
        }
        for (int i = 1; i < n; ++i) {
            for (int j = i - 1; j >= 0; --j) {
                int k = stones[i] - stones[j];
                if (k > j + 1) {
                    break;
                }
                dp[i][k] = dp[j][k - 1] || dp[j][k] || dp[j][k + 1];
                if (i == n - 1 && dp[i][k]) {
                    return true;
                }
            }
        }
        return false;
    }
}
